package com.dmall.chapter07.section06;

import java.util.*;

public class LeetCode773 {

    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int zero = -1;

    public int slidingPuzzle(int[][] board) {

        Queue<String> queue = new LinkedList<>();
        HashMap<String, Integer> visited = new HashMap<>();

        String s = boardToString(board);
        if ("123450".equals(s)) {
            return 0;
        }

        queue.add(s);
        visited.put(s, 0);

        while (!queue.isEmpty()) {
            String cur = queue.remove();
            ArrayList<String> nexts = getNexts(cur);
            for (String next : nexts) {
                if (!visited.containsKey(next)) {
                    queue.add(next);
                    visited.put(next, visited.get(cur) + 1);
                    if (next.equals("123450")) {
                        return visited.get(next);
                    }
                }
            }
        }
        return -1;
    }

    private ArrayList<String> getNexts(String s) {
        int[][] board = stringToBoard(s);
        ArrayList<String> result = new ArrayList<>();

        int zx = zero / 3;
        int zy = zero % 3;

        for (int i = 0; i < dirs.length; i++) {
            int nextx = zx + dirs[i][0];
            int nexty = zy + dirs[i][1];
            if (inArea(nextx, nexty)) {
                swap(board, zx, zy, nextx, nexty);
                result.add(boardToString(board));
                swap(board, zx, zy, nextx, nexty);
            }
        }

        return result;
    }

    private void swap(int[][] board, int x, int y, int swapx, int swapy) {
        int temp = board[x][y];
        board[x][y] = board[swapx][swapy];
        board[swapx][swapy] = temp;
    }

    private boolean inArea(int x, int y) {
        return x >=0 && x < 2 && y >= 0 && y < 3;
    }

    private int[][] stringToBoard(String s) {
        int[][] board = new int[2][3];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                char cur = s.charAt(i * 3 + j);
                board[i][j] = cur - '0';
                if (cur == '0') {
                    zero = i * 3 + j;
                }
            }
        }
        return board;
    }

    private String boardToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LeetCode773 leetCode773 = new LeetCode773();
        int[][] board = {{1, 2, 3}, {5, 4, 0}};
        System.out.println(leetCode773.slidingPuzzle(board));
    }
}
